1. Field of the Invention
The present invention relates generally to congestion control during data transfer and, more particularly, to systems and methods for performing dequeuing and congestion control on single stream multicast data.
2. Description of Related Art
Conventional network devices, such as routers, relay streams of data through a network from a source to a destination. Typically, the network devices include one or more memory subsystems to temporarily buffer data while the network devices perform network-related functions, such as route processing or accounting.
A data stream may be considered a pipe of data packets belonging to a communication between a particular source and one or more particular destinations. A network device may assign a variable number of queues (e.g., where a queue may be considered a logical first-in, first-out (FIFO) buffer) to a data stream. For a stream with n queues, the relationship of queues and streams may be represented by:
      stream    bandwidth    =            ∑      0              n        -        1              ⁢                  queue        bandwidth            .      
A problem that may arise in the use of queues is that congestion occurs if data builds up too quickly in the queues (i.e., data is enqueued at a faster rate than it is dequeued). Network devices typically address this problem by notifying sources of the packets of the congestion. This notification sometimes takes the form of dropping more recent packets received from the sources. It is sometimes a difficult and time-consuming process, however, to decide whether to drop a packet from a queue.
Additional problems result when single stream multicast packets are present. A single stream multicast packet is a packet from a single source to multiple different destinations within the same given stream. An example might include multiple frame relay circuits within a physical stream. Conventional network devices handle single stream multicast packets by replicating the packets an appropriate number of times. Each of the replicated packets corresponds to one of the different destinations. The network devices then store the replicated packets in a queue and send them out one replicated packet at a time.
To store and process the replicated packets, a significant amount of resources (e.g., memory) must be used. Memory is typically a valuable resource in a network device. As a result, it is important to efficiently use memory during processing of packets, including single stream multicast packets, by the network device.
Therefore, there is a need for efficient mechanisms for storing and processing single stream multicast packets.